package 单调栈;

import java.util.*;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/4/7 14:07
 */
public class leetcode {

    /*
    面试中碰到了一个题：在数组中找出所有这样的数，它比它前面的数都大，比它后面的数都小，要求时间复杂度是n。
    我只想到了暴力求解复杂度还是n^2的

     */


        public static void main(String[] args) throws Exception {
            for (int i = 0; i < 100; i++) {
                Random r = new Random();
                int len = r.nextInt(100);
                int[] test = new int[len];
                for (int j = 0; j < len; j++) {
                    test[j] = r.nextInt(100000);
                }
                List<Integer> res1 = method(test);
                List<Integer> res2 = method1(test);
                if (res1.size() != res2.size() || !res1.equals(res2)) {
                    System.out.println("res1 = " + res1);
                    System.out.println("res2 = " + res2);
                    System.out.println("test = " + Arrays.toString(test));
                }
            }
        }

        public static List<Integer> method1(int[] arr) {
            List<Integer> res = new ArrayList<>();
            for (int i = 0; i < arr.length; i++) {
                boolean flag = true;
                //左边比自己大的
                for (int j = i - 1; j >= 0; j--) {
                    if (arr[j] >= arr[i]) {
                        flag = false;
                        break;
                    }
                }
                if (!flag) {
                    continue;
                }
                //右边比自己小的
                for (int j = i + 1; j < arr.length; j++) {
                    if (arr[j] <= arr[i]) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    res.add(i);
                }
            }
            return res;
        }

        public static List<Integer> method(int[] arr) {
            int len = arr.length;
            int[] leftBig = new int[len];
            int[] rightSmall = new int[len];
            //单调递增
            Deque<Integer> stack = new LinkedList<>();
            Arrays.fill(leftBig, -1);
            Arrays.fill(rightSmall, -1);
            for (int i = 0; i < len; i++) {
                if (stack.isEmpty()) {
                    stack.push(i);
                    continue;
                }
                while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
                    int pop = stack.pop();
                    rightSmall[pop] = i;
                    leftBig[i] = pop;
                }
                stack.push(i);
            }
            //单调递减
            stack = new LinkedList<>();
            for (int i = len - 1; i >= 0; i--) {
                if (stack.isEmpty()) {
                    stack.push(i);
                    continue;
                }
                while (!stack.isEmpty() && arr[stack.peek()] <= arr[i]) {
                    int pop = stack.pop();
                    leftBig[pop] = i;
                    rightSmall[i] = pop;
                }
                stack.push(i);
            }
            List<Integer> res = new ArrayList<>();
            for (int i = 0; i < len; i++) {
                if (leftBig[i] == -1 && rightSmall[i] == -1) {
                    res.add(i);
                }
            }
            return res;
        }

}
